package code1_100.code20_30;

import java.util.ArrayList;
import java.util.List;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：["()"]
 *
 */
public class _22generateParenthesis {


    public static List<String> result = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        result.clear();
        dfs(n,0,0,"");
        return result;
    }

    public static void dfs(int n,int left,int right,String str){
        // left表示左括号，right表示右括号。直接深搜即可，不需要回溯
        if(left==n&&right==n){
            result.add(str);
        }else {
            if(left<n){
                dfs(n,left+1,right,str+"(");
            }
            if(right<n&&left>right){
                dfs(n,left,right+1,str+")");
            }
        }
    }

}
